class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

'''
迭代实现
'''
def reverseList(head):
    prev = None
    curr = head
    while curr:
        #保存当前节点的下一个节点
        next_temp = curr.next
        #反转指针
        curr.next = prev
        #移动prev和curr
        prev = curr
        curr = next_temp
    return prev

'''
递归实现
'''
def reverseList2(head):
    #递归终止条件：当链表为空或只有一个节点
    if(head is None or head.next is None):
        return head

    #递归反转head.next子链表，并获取反转后的头节点
    new_head = reverseList2(head.next)

    #将head.next指向None
    head.next = None

    #将反转后的子链表的头节点（原链表的第二个节点）的next指向head
    #这一步实现了链表的反转连接
    new_head.next = head

    #返回反转后的链表的头节点
    return new_head

#示例
#创建链表 1->2->3->5->4
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(5)
head.next.next.next.next = ListNode(4)

#反转链表迭代
current = reverseList(head)
while current:
    if current != None:
        print(current.val,end = '->')
        current = current.next
print(None)

#创建链表 1->2->5->3->4
head1 = ListNode(1)
head1.next = ListNode(2)
head1.next.next = ListNode(5)
head1.next.next.next = ListNode(3)
head1.next.next.next.next = ListNode(4)

#反转链表递归
current1 = reverseList2(head1)
while current1:
    print(current1.val,end = '->')
    current1 = current1.next
